package day190411;

import java.util.Arrays;

/**
 * @author LI DUO
 * @date 2019/4/11 下午 07:54
 */
public class MergeSort {

    public void mergeSort(int[] a, int n) {
        mergeSort_c(a, 0, n - 1);
    }

    public void mergeSort_c(int[] a, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = p + (r - p) / 2;

        mergeSort_c(a, p, q);
        mergeSort_c(a, q + 1, r);

        merge(a, p, q , r);
    }

    public void merge(int[] a, int left, int right, int length) {
        int i = left;
        int j = right + 1;
        int k = 0;
        int[] tmp = new int[length - left + 1];
        while (i <= right && j <= length) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                tmp[k++] = a[j++];
            }
        }
        int start = i;
        int end = right;
        if (j <= length) {
            start = j;
            end = length;
        }
        while (start <= end) {
            tmp[k++] = a[start++];
        }
        for (i = 0; i <= length - left; i ++) {
            a[left + i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        MergeSort sort = new MergeSort();
        int[] a = new int[]{1, 5, 6, 2, 3, 4};
        sort.mergeSort(a, a.length);
        System.out.println(Arrays.toString(a));
    }
}
